package com.dtx.leetcode.rookie;

/**
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 *
 * 如果有两个中间结点，则返回第二个中间结点。
 *
 * 示例 1：
 *
 * 输入：[1,2,3,4,5]
 * 输出：此列表中的结点 3 (序列化形式：[3,4,5])
 * 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
 * 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
 * ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
 * 示例2：
 *
 * 输入：[1,2,3,4,5,6]
 * 输出：此列表中的结点 4 (序列化形式：[4,5,6])
 * 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
 *
 * 提示：
 *
 * 给定链表的结点数介于1和100之间。
 */
public class A4 {

    public static void main(String[] args) {

        ListNode listNode = createListNode();
        //ListNode.print(listNode);
        ListNode node = middleNode(listNode);
        System.out.println(node);
    }

    public static ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private static ListNode createListNode(){
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;

        return node1;
    }

      private static class ListNode {
          public int val;
          public ListNode next;

          public ListNode() {}

          public ListNode(int val) {this.val = val;}

          public ListNode(int val, ListNode next) {
              this.val = val;
              this.next = next;
          }

          @Override
          public String toString() {
              return "ListNode{" +
                      "val=" + val +
                      '}';
          }

          public static void print(ListNode node){
              if (node == null) {
                  return;
              }
              ListNode temp = node;
              while (temp != null) {
                  System.out.println(temp.val);
                  temp = temp.next;
              }
          }
      }

}
